 /*******************************************************************************
  * Copyright (c) 2005 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.core.internal.preferences;

 import org.eclipse.core.internal.preferences.StringPool;

 /**
  * Hash table of {String --> String}.
  *
  * This map handles collisions using linear probing. When elements are
  * removed, the entire table is rehashed. Thus this map has good space
  * characteristics, good insertion and iteration performance, but slower
  * removal performance than a HashMap.
  * <p>
  * This map is thread safe because it is immutable. All methods that modify
  * the map create and return a new map, rather than modifying the receiver.
  */
 public abstract class ImmutableMap implements Cloneable {
     static class ArrayMap extends ImmutableMap {
         private static final float LOAD_FACTOR = 0.45f;
         /**
          * number of elements in the table
          */
         private int elementSize;

         /**
          * The table keys
          */
         private String [] keyTable;

         private int threshold;
         private String [] valueTable;

         ArrayMap(int size) {
             this.elementSize = 0;
             //table size must always be a power of two
 int tableLen = 1;
             while (tableLen < size)
                 tableLen *= 2;
             this.keyTable = new String [tableLen];
             this.valueTable = new String [tableLen];
             this.threshold = (int) (tableLen * LOAD_FACTOR);
         }

         public String get(String key) {
             int lengthMask = keyTable.length - 1;
             int index = key.hashCode() & lengthMask;
             String currentKey;
             while ((currentKey = keyTable[index]) != null) {
                 if (currentKey.equals(key))
                     return valueTable[index];
                 index = (index + 1) & lengthMask;
             }
             return null;
         }

         /**
          * This method destructively adds the key/value pair to the table.
          * The caller must ensure the table has an empty slot before calling
          * this method.
          * @param key
          * @param value
          */
         protected void internalPut(String key, String value) {
             int lengthMask = keyTable.length - 1;
             int index = key.hashCode() & lengthMask;
             String currentKey;
             while ((currentKey = keyTable[index]) != null) {
                 if (currentKey.equals(key)) {
                     valueTable[index] = value;
                     return;
                 }
                 index = (index + 1) & lengthMask;
             }
             keyTable[index] = key;
             valueTable[index] = value;
             ++elementSize;
         }

         /**
          * Returns an array of all keys in this map.
          */
         public String [] keys() {
             if (elementSize == 0)
                 return EMPTY_STRING_ARRAY;
             String [] result = new String [elementSize];
             int next = 0;
             for (int i = 0; i < keyTable.length; i++)
                 if (keyTable[i] != null)
                     result[next++] = keyTable[i];
             return result;
         }

         public ImmutableMap put(String key, String value) {
             ArrayMap result;
             final int oldLen = keyTable.length;
             if (elementSize + 1 > threshold) {
                 //rehash case
 String currentKey;
                 result = new ArrayMap(oldLen * 2);
                 for (int i = oldLen; --i >= 0;)
                     if ((currentKey = keyTable[i]) != null)
                         result.internalPut(currentKey, valueTable[i]);
             } else {
                 result = new ArrayMap(oldLen);
                 System.arraycopy(this.keyTable, 0, result.keyTable, 0, this.keyTable.length);
                 System.arraycopy(this.valueTable, 0, result.valueTable, 0, this.valueTable.length);
                 result.elementSize = this.elementSize;
             }
             result.internalPut(key, value);
             return result;
         }

         public ImmutableMap removeKey(String key) {
             final int lengthMask = keyTable.length - 1;
             int index = key.hashCode() & lengthMask;
             String currentKey;
             while ((currentKey = keyTable[index]) != null) {
                 if (currentKey.equals(key)) {
                     if (elementSize <= 1)
                         return EMPTY;
                     //return a new map that includes all keys except the current one
 ImmutableMap result = createMap((int) (elementSize / LOAD_FACTOR));
                     for (int i = 0; i < index; i++)
                         if ((currentKey = keyTable[i]) != null)
                             result.internalPut(currentKey, valueTable[i]);
                     for (int i = index + 1; i <= lengthMask; i++)
                         if ((currentKey = keyTable[i]) != null)
                             result.internalPut(currentKey, valueTable[i]);
                     return result;
                 }
                 index = (index + 1) & lengthMask;
             }
             return this;
         }

         /* (non-Javadoc
          * Method declared on IStringPoolParticipant
          */
         public void shareStrings(StringPool set) {
             //copy elements for thread safety
 String [] array = keyTable;
             if (array == null)
                 return;
             for (int i = 0; i < array.length; i++) {
                 String o = array[i];
                 if (o != null)
                     array[i] = set.add(o);
             }
             array = valueTable;
             if (array == null)
                 return;
             for (int i = 0; i < array.length; i++) {
                 String o = array[i];
                 if (o != null)
                     array[i] = set.add(o);
             }
         }

         public int size() {
             return elementSize;
         }

     }

     static class EmptyMap extends ImmutableMap {
         public String get(String value) {
             return null;
         }

         public ImmutableMap removeKey(String key) {
             return this;
         }
         
         protected void internalPut(String key, String value) {
             throw new IllegalStateException ();//cannot put elements in the empty map
 }

         public String [] keys() {
             return EMPTY_STRING_ARRAY;
         }

         public ImmutableMap put(String key, String value) {
             ImmutableMap result = createMap(4);
             result.internalPut(key, value);
             return result;
         }

         public int size() {
             return 0;
         }
     }

     /**
      * The empty hash map. Since instances are immutable, the empty map
      * can be a singleton, with accessor methods optimized for the empty map case.
      */
     public static final ImmutableMap EMPTY = new EmptyMap();

     protected static final String [] EMPTY_STRING_ARRAY = new String [0];

     /**
      * Returns the value associated with this key in the map, or
      * <code>null</code> if the key is not present in the map.
      * @param key
      * @return The value associated with this key, or <code>null</code>
      */
     public abstract String get(String key);
     
     protected static ImmutableMap createMap(int i) {
         if (i <= 0)
             return EMPTY;
         return new ArrayMap(i);
     }

     /**
      * Destructively adds a key/value pair to this map. The caller must ensure
      * there is enough room in this map to proceed.
      *
      * @param key
      * @param value
      */
     protected abstract void internalPut(String key, String value);

     /**
      * Returns an array of all keys in this map.
      */
     public abstract String [] keys();

     /**
      * Returns a new map that is equal to this one, except with the given
      * key/value pair added.
      *
      * @param key
      * @param value
      * @return The map containing the given key/value pair
      */
     public abstract ImmutableMap put(String key, String value);

     /**
      * Returns a map that is equal to this one, except without the given
      * key.
      * @param key
      * @return A map with the given key removed
      */
     public abstract ImmutableMap removeKey(String key);

     /* (non-Javadoc
      * Method declared on IStringPoolParticipant
      */
     public void shareStrings(StringPool set) {
     }

     /**
      * Returns the number of keys in this map.
      * @return the number of keys in this map.
      */
     public abstract int size();

     public String toString() {
         StringBuffer s = new StringBuffer ();
         String [] keys = keys();
         for (int i = 0, length = keys.length; i < length; i++)
             s.append(keys[i]).append(" -> ").append(get(keys[i])).append("\n"); //$NON-NLS-2$ //$NON-NLS-1$
 return s.toString();
     }
 }

